package leetcode.editor.cn;

import java.util.Arrays;

/**
 * @author: yangwk
 * @date: 2023/10/18
 * @description:
 **/
//Winter is coming! During the contest, your first job is to design a standard heater with a fixed warm radius to warm all the houses.
//
//        Every house can be warmed, as long as the house is within the heater's warm radius range.
//
//        Given the positions of houses and heaters on a horizontal line, return the minimum radius standard of heaters so that those heaters could cover all houses.
//
//        Notice that all the heaters follow your radius standard, and the warm radius will the same.


public class P475 {
    public static void main(String[] args) {
        int[] houses = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21};
        int[] heaters = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21};
        System.out.println(findRadius(houses, heaters));
    }

    public static int findRadius(int[] houses, int[] heaters) {
        int houseIndex = 0;
        int heaterIndex = 0;
        int max = Integer.MIN_VALUE;
        Arrays.sort(houses);
        Arrays.sort(heaters);
        while (houseIndex < houses.length) {
            int radius = Math.abs(houses[houseIndex] - heaters[heaterIndex]);
            while (heaterIndex < heaters.length - 1 && Math.abs(houses[houseIndex] - heaters[heaterIndex]) >= Math.abs(houses[houseIndex] - heaters[heaterIndex + 1])) {
                heaterIndex++;
                radius = Math.min(radius, Math.abs(houses[houseIndex] - heaters[heaterIndex]));
            }
            max = Math.max(radius, max);
            houseIndex++;
        }
        return max;
    }
}

